/*
 * @Author: kaikaima
 * @Date: 2020-12-29 15:09:06
 * @LastEditTime: 2021-01-04 21:01:40
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: /undefined/home/messi/Data_Structure_and_Algorithm_GIT/Tree/IntervalTree/Interval.h
 */
#ifndef __hhxxttxs_INTERVAL__
#define __hhxxttxs_INTERVAL__

#include <iostream>

#define BLACK true
#define RED false

template <class T>
class interval
{
public:
    class zone{
    public:
        T low;
        T high;
        zone() {};
        zone(T _data1, T _data2) {low=(_data1<=_data2)?(_data1):(_data2); high=_data1+_data2-low;};
    };
protected:
    class Node{
    public:
	Node* lc;
	Node* rc;
	Node* parent;
    zone data;
    T key;//the maximum right endpoint
    bool color;
    Node() {lc=rc=parent=NULL; color=BLACK;};
    Node(zone _data);
    };
    Node* root;    
    Node* nil;
    void release(Node* _x);
    Node* search(T _data1, T _data2) const;
    Node* min(Node* _x) const;
    Node* max(Node* _x) const;
    void inorder_walk(Node* _x) const;
    Node* data_insert(zone _data);
    void updatekey(Node* _x);
    void DEL(Node* _x);
    void right_rotation (Node* _x);
    void left_rotation (Node* _x);
    void recolor (Node* _x);
public:
    interval() {nil=new Node; nil->color=BLACK; nil->parent=nil->lc=nil->rc=nil; root=nil;};
    interval(T _data1, T _data2);
    interval(zone _data);
    ~interval();
    void insert(T _data1, T _data2);
    void insert(zone _data);
    void inorder_walk() const;
    void del(T _data1, T _data2);
    void del(zone _data);
    void intersect(T _low, T _high) const;
    void intersect(zone _data) const;
};

/**
 * @description: default color is red
 * @param {*} two data
 * @return {*} get an interval
 */
template <class T>
interval<T>::Node::Node(zone _data)
{
    data=_data;
    parent = lc = rc = NULL;
    key=data.high;
    color = RED;
};

template <class T>
void interval<T>::release(Node* _x)
{
    if (_x != nil)
    {
	release(_x->lc);
	release(_x->rc);
	delete _x;
    }	
};

template <class T>
typename interval<T>::Node* interval<T>::search(T _data1, T _data2) const
{
    Node* p = root;
    T min=(_data1<=_data2)?(_data1):(_data2);
    while (p != nil){
    if(p->data.low < min)
    p = p->rc;
    else if(p->data.low > min)
    p = p->lc;
    else if(p->data.high == _data1+_data2-min)
    break;}
    if(p==nil)
    return NULL;
    return p;
};

template <class T>
typename interval<T>::Node* interval<T>::min(Node* _x) const
{
    while (_x->lc != nil)
	_x = _x->lc;
    return _x;
};

template <class T>
typename interval<T>::Node* interval<T>::max(Node* _x) const
{
    while (_x->rc != nil)
	_x = _x->rc;
    return _x;
};

template <class T>
void interval<T>::inorder_walk(Node* _x) const
{
    if (_x != nil)
    {
	inorder_walk(_x->lc);
	std::cout <<"("<<_x->data.low<<","<<_x->data.high<<")"<<"\t";
	inorder_walk(_x->rc);
    }
};

template <class T>
typename interval<T>::Node* interval<T>::data_insert(zone _data)
{
    Node* y = nil;
    Node* x = root;
    Node* p = new Node(_data);
    p->lc = p->rc = p->parent = nil;
    while (x != nil){
	y = x;
    if(p->data.high > x->key)
    x->key=p->data.high;
	if (p->data.low < x->data.low)
	x = x->lc;
	else
	x = x->rc;
    }
    p->parent = y;
    if (y == nil){
        root = p;
        p->color=BLACK;
    }
    else 
    (p->data.low < y->data.low)?(y->lc=p):(y->rc=p);
    return p;
};

template <class T>
void interval<T>::updatekey(Node* _x)
{
    T max;
    Node* p =_x;
    while(p!=nil && p->parent->key==_x->key){
        max=_x->parent->data.high;
        if(p->parent->lc!=nil && p->parent->lc!=_x && max<p->parent->lc->key)
        max=p->parent->lc->key;
        if(p->parent->rc!=nil && p->parent->rc!=_x && max<p->parent->rc->key)
        max=p->parent->rc->key;
        p->parent->key=max;
        p=p->parent;
    }
}

template <class T>
void interval<T>::DEL(Node* _x)
{
    if(_x==NULL || _x==this->nil)
        return;
    if(_x->lc==_x->rc/*==this->nil*/){
        if(_x->color==RED)//_x will not be the root
        {
            if(_x==_x->parent->lc)
            _x->parent->lc=nil;
            else
            _x->parent->rc=nil;
            updatekey(_x);
            delete _x;
        }
        else
        {
            Node* x=_x->rc;
            if(_x->parent == nil)
                root=_x->rc;
            else if(_x==_x->parent->lc)
                _x->parent->lc=_x->rc;
            else
                _x->parent->rc=_x->rc;
            _x->rc->parent=_x->parent;
            updatekey(_x);
            delete _x;
            while(x!=this->root && x->color==BLACK){
                bool key = (x==x->parent->lc);
                Node* brother=(x==x->parent->lc)?(x->parent->rc):(x->parent->lc);
                if(brother->color==RED){
                    brother->color=BLACK;
                    x->parent->color=RED;
                    if(key){
                    left_rotation(x->parent);
                    brother=x->parent->rc;}
                    else{
                    right_rotation(x->parent);
                    brother=x->parent->lc;}
                }
                if(brother->lc->color==BLACK && brother->rc->color==BLACK){
                    brother->color=RED;
                    x=x->parent;}
                else if(key){
                    if(brother->rc->color==BLACK){
                        brother->lc->color=BLACK;
                        brother->color=RED;
                        right_rotation(brother);
                        brother=x->parent->rc;
                    }
                    brother->color=x->parent->color;
                    x->parent->color=BLACK;
                    brother->rc->color=BLACK;
                    left_rotation(x->parent);
                    x=root;
                }
                else{
                    if(brother->lc->color==BLACK){
                        brother->rc->color=BLACK;
                        brother->color=RED;
                        left_rotation(brother);
                        brother=x->parent->rc;
                        }
                    brother->color=x->parent->color;
                    x->parent->color=BLACK;
                    brother->lc->color=BLACK;
                    right_rotation(x->parent);
                    x=root;
                }
            }
        }
        return;
    }
    if(_x->lc==nil || _x->rc==nil)
    /**
     * @description: based on the red-black properties, _x must be black with a red child and don't have grandson.
     * @param {*}
     * @return {*}
     */
    {
        Node* child = (_x->lc==this->nil)?(_x->rc):(_x->lc);
        _x->data=child->data;
        _x->lc=_x->rc=this->nil;
        _x->key=_x->data.high;
        updatekey(child);
        delete child;
    }
    else{
        Node* p = this->min(_x->rc);
        _x->data=p->data;
        DEL(p);//p will not have left child
    }
};


template <class T>
void interval<T>::right_rotation(interval<T>::Node* _x)
{
    Node* _y = _x->lc;
    _x->lc=_y->rc;
    if(_y->rc!=nil)
    _y->rc->parent=_x;
    _y->parent=_x->parent;
    if(_x->parent==nil)
    root=_y;
    else
    {
        (_x->parent->lc==_x)?(_x->parent->lc):(_x->parent->rc)=_y;
    }
    _y->rc=_x;
    _x->parent=_y;
    _y->key=_x->key;
    T max=(_x->lc->key>_x->rc->key)?(_x->lc->key):(_x->rc->key);
    max=(max>_x->data.high)?(max):(_x->data.high);
    _x->key=max;
};

template <class T>
void interval<T>::left_rotation(interval<T>::Node* _x)
{
    Node* _y = _x->rc;
    _x->rc=_y->lc;
    if(_y->lc!=nil)
    _y->lc->parent=_x;
    _y->parent=_x->parent;
    if(_x->parent==nil)
    root=_y;
    else
    {
        (_x->parent->lc==_x)?(_x->parent->lc):(_x->parent->rc)=_y;
    }
    _y->lc=_x;
    _x->parent=_y;
    _y->key=_x->key;
    T max=(_x->lc->key>_x->rc->key)?(_x->lc->key):(_x->rc->key);
    max=(max>_x->data.high)?(max):(_x->data.high);
    _x->key=max;
};

template <class T>
void interval<T>::recolor(interval<T>::Node* _x)
{
    if(_x->rc->color==RED && _x->lc->color==RED)
    {
        _x->color=RED;
        _x->rc->color=_x->lc->color=BLACK;
    }  
};


/*
 *                     江城子 . 分割符
 *           ————上面是private，下面是public
 * 
 *               十年生死两茫茫，写程序，到天亮。
 *                    千行代码，Bug何处藏。
 *               纵使码完又怎样，朝令改，夕断肠。
 * 
 *               老师每周新作业，天天改，日日忙。
 *                    相顾无言，惟有泪千行。
 *               每晚灯火阑珊处，夜难寐，加班狂。
 * 
 */


template <class T>
interval<T>::interval(T _data1, T _data2)
{
    nil=new Node;
    nil->color=BLACK;
    zone _data(_data1,_data2);
    Node* p = new Node(_data);
    p->lc=p->rc=p->parent=nil;
    p->color=BLACK;
    root=p;
};

template <class T>
interval<T>::interval(zone _data)
{
    nil=new Node;
    nil->color=BLACK;
    Node* p =new Node(_data);
    p->lc=p->rc=p->parent=nil;
    p->color=BLACK;
    root=p;
};

template <class T>
interval<T>::~interval()
{
    release(root);
    delete nil;
};

template <class T>
void interval<T>::insert(T _data1, T _data2)
{
    zone _data(_data1,_data2);
    insert(_data);
};

template <class T>
void interval<T>::insert(zone _data)
{
    if(root==nil){
        Node* p = new Node(_data);
        p->parent=p->lc=p->rc=nil;
        p->color=BLACK;
        root=p;
        return;
    }
    Node* z = data_insert(_data);
    while(z->parent->color==RED)//z has its grandpa because root's color is black
    {
    if(z->parent==z->parent->parent->lc){
        Node* uncle=z->parent->parent->rc;
        if(uncle->color==RED){
            recolor(z->parent->parent);
        /**
         * @description: then rejudge uncle's parent.
         * @param {*}
         * @return {*}
         */
            z=z->parent->parent;
        }
        else{
        if(z==z->parent->rc){
            /**
             * @description: z always points the third-generation.
             * @param {*}
             * @return {*}
             */
            z=z->parent;
            left_rotation(z);
        }
        z->parent->color=BLACK;
        z->parent->parent->color=RED;
        right_rotation(z->parent->parent);
        break;
        }}
    else
    /**
     * @description: do the same thing expect changing left and right
     * @param {*}
     * @return {*}
     */
    {
        Node* uncle=z->parent->parent->lc;
        if(uncle->color==RED){
            recolor(z->parent->parent);
            z=z->parent->parent;
        }
        else{
        if(z==z->parent->lc){
            z=z->parent;
            right_rotation(z);
        }
        z->parent->color=BLACK;
        z->parent->parent->color=RED;
        left_rotation(z->parent->parent);
        break;
        }}
    }
    this->root->color=BLACK;
};

template <class T>
void interval<T>::inorder_walk() const
{
    if (root != nil)
	inorder_walk(root);
    else
    std::cout<<"It's an empty tree. ";
    std::cout<<std::endl;
};

template <class T>
void interval<T>::del(T _data1, T _data2)
{
    DEL(search(_data1, _data2));
}

template <class T>
void interval<T>::del(zone _data)
{
    DEL(search(_data.low, _data.high));
};

template <class T>
void interval<T>::intersect(T _low, T _high) const{
    Node* p = root;
    while(p!=nil && _low>=p->data.high || _high<=p->data.low){
    if(p->lc!=nil && _low<=p->lc->key)
    p=p->lc;
    else
    p=p->rc;}
    if(p!=nil)
    std::cout<<"("<<p->data.low<<","<<p->data.high<<")"<<std::endl;
    else
    std::cout<<"There is no interval intersecting with it. "<<std::endl;
};

template <class T>
void interval<T>::intersect(zone _data) const{
    Node* p = root;
    while (p != nil && (_data.low >= p->data.high || _data.high <= p->data.low)){
    if(p->lc != nil && _data.low <=p->lc->key)
    p = p->lc;
    else
    p = p->rc;}
    if(p!=nil)
    std::cout<<"("<<p->data.low<<","<<p->data.high<<")"<<std::endl;
    else
    std::cout<<"There is no interval intersecting with it. "<<std::endl;
};

#else
//do nothing
#endif